/*  This file is part of TextEditorLibrary - a library for the programmatic manipulation of text.

    TextEditorLibrary is free software: you can redistribute it and/or modify it under the terms
    of the GNU Lesser General Public License as published by the Free Software Foundation, either
    version 3 of the License, or (at your option) any later version.

    TextEditorLibrary is distributed in the hope that it will be useful, but WITHOUT ANY 
    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
    PURPOSE.  See the GNU Lesser General Public License for more details at 
    <http://www.gnu.org/licenses/>.
*/

using System;
using System.Collections.Generic;
using System.Text;

namespace TextEditorLibrary
{
    internal enum PatternType
    {
        True,
        False,
        BeginLine,
        EndLine,
        BeginWord,
        BeginWord7,
        EndWord,
        EndWord7,
        Any,
        Letter,
        Upper,
        Lower,
        Digit,
        Control,
        Punctuation,
        Symbol,
        White,
        Text,
        Span,
        AnyOf,
        AnyBut,
        Same,
        Repeat,
        And,
        Or,
        Not,
        Save,
        Set,
        Plus,
        Minus,
        Equals,
        NotEqual,
        Less,
        Greater,
        LessEqual,
        GreaterEqual,
        Delegate
    }

/// <summary>Defines a hierarchical structure for complex recursive pattern-matching.</summary>
    public class Pattern
    {
        private static int _IDs = 0;            // Number of Patterns so far
        private static bool _exact = true;      // Default value for exact match argument if not specified

        private int _ID;                        // Pattern ID for debug
        internal PatternType _patternType;      // Type of Pattern
        internal Mark _searchMark;              // Saved position for FindAgain

        internal Pattern(PatternType patternType)
        {
            _ID = ++_IDs;
            _patternType = patternType;
        }

    //---------------------------------------------------------------------------------------------

    /// <summary>Specifies a default value for exact matching applying to any new Pattern when the
    /// exact argument is not specified in the constructor.</summary>
        public static bool Exact
        {
            get { return _exact; }
            set { _exact = value; }
        }

    //---------------------------------------------------------------------------------------------

    // Basic Pattern creators

    /// <summary>Creates a Pattern which always matches, for example for use with Or to match
    /// an optional element.</summary>
        public static Pattern True()
        {
            return new Pattern(PatternType.True);
        }

    /// <summary>Creates a Pattern which always fails to match, used for example to terminate an
    /// unlimited Repeat.</summary>
        public static Pattern False()
        {
            return new Pattern(PatternType.False);
        }

    /// <summary>Creates a Pattern which always matches or fails to match according to the current
    /// value of the argument.</summary>
    /// <param name="flag">bool value indicating whether to match or not to match.</param>
        public static implicit operator Pattern(bool flag)
        {
            if (flag) return new Pattern(PatternType.True);
            else return new Pattern(PatternType.False);
        }

    /// <summary>Creates a Pattern which matches the beginning of a line (at the start of the
    /// Text or following a newline character).</summary>
        public static Pattern BeginLine()
        {
            return new Pattern(PatternType.BeginLine);
        }

    /// <summary>Creates a Pattern which matches the end of a line (preceding a newline character
    /// or at the end of the Text).</summary>
        public static Pattern EndLine()
        {
            return new Pattern(PatternType.EndLine);
        }

    /// <summary>Creates a Pattern which matches the beginning of a word (between a non-word
    /// character and a word character, where a word character is a letter, digit or underscore).
    /// </summary>
        public static Pattern BeginWord()
        {
            return new Pattern(PatternType.BeginWord);
        }

    /// <summary>Creates a Pattern which matches the beginning of a 7-bit (Basic Latin) word (between a 
    /// non-word character and a word character, where a word character is a Basic Latin letter, digit
    /// or underscore).</summary>
        public static Pattern BeginWord7()
        {
            return new Pattern(PatternType.BeginWord7);
        }

    /// <summary>Creates a Pattern which matches the end of a word (between a word character and
    /// a non-word character, where a word character is a letter, digit or underscore).</summary>
        public static Pattern EndWord()
        {
            return new Pattern(PatternType.EndWord);
        }

    /// <summary>Creates a Pattern which matches the end of a 7-bit (Basic Latin) word (between a 
    /// word character and a non-word character, where a word character is a Basic Latin letter, digit
    /// or underscore).</summary>
        public static Pattern EndWord7()
        {
            return new Pattern(PatternType.EndWord7);
        }

    /// <summary>Creates a Pattern which matches any character including newline characters.
    /// </summary>
        public static Pattern Any()
        {
            return new Pattern(PatternType.Any);
        }

    /// <summary>Creates a Pattern which matches any letter as determined by Char.IsLetter().
    /// </summary>
        public static Pattern Letter()
        {
            return new Pattern(PatternType.Letter);
        }

    /// <summary>Creates a Pattern which matches any upper-case letter as determined by
    /// Char.IsUpper().</summary>
        public static Pattern Upper()
        {
            return new Pattern(PatternType.Upper);
        }

    /// <summary>Creates a Pattern which matches any lower-case letter as determined by
    /// Char.IsLower().</summary>
        public static Pattern Lower()
        {
            return new Pattern(PatternType.Lower);
        }

    /// <summary>Creates a Pattern which matches any digit as determined by Char.IsDigit().
    /// </summary>
        public static Pattern Digit()
        {
            return new Pattern(PatternType.Digit);
        }

    /// <summary>Creates a Pattern which matches any control character as determined by 
        /// Char.IsControl().</summary>
        public static Pattern Control()
        {
            return new Pattern(PatternType.Control);
        }

    /// <summary>Creates a Pattern which matches any punctuation character as determined by 
    /// Char.IsPunctuation().</summary>
        public static Pattern Punctuation()
        {
            return new Pattern(PatternType.Punctuation);
        }
 
    /// <summary>Creates a Pattern which matches any symbol character as determined by 
    /// Char.IsSymbol().</summary>
        public static Pattern Symbol()
        {
            return new Pattern(PatternType.Symbol);
        }


    /// <summary>Creates a Pattern which matches any whitespace character as determined by
    /// Char.IsWhiteSpace().</summary>
        public static Pattern White()
        {
            return new Pattern(PatternType.White);
        }

    /// <summary>Creates a Pattern which matches given text.</summary>
    /// <param name="text">string to match.</param>
    /// <param name="exact">bool indicating whether case and diacritical marks should be
    /// respected.</param>
        public static Pattern Text(string text, bool exact)
        {
            return new StringPattern(PatternType.Text, text, exact, null, null);
        }

    /// <summary><para>Creates a Pattern which matches given text.</para>
    /// <para>Case and diacritical marks will be respected if the static Pattern property
    /// Exact is set to true.</para></summary>
    /// <param name="text">string to match.</param>
        public static Pattern Text(string text)
        {
            return new StringPattern(PatternType.Text, text, _exact, null, null);
        }

    /// <summary>Creates a Pattern which matches a given character.</summary>
    /// <param name="text">char to match. The match is exact</param>
        public static Pattern Text(char text)
        {
            return new StringPattern(PatternType.Text, text.ToString(), true, null, null);
        }

    /// <summary><para>Creates a Pattern which matches given text.</para>
    /// <para>Case and diacritical marks will be respected if the static Pattern property
    /// Exact is set to true.</para></summary>
    /// <param name="text">string to match.</param>
        public static implicit operator Pattern(string text)
        {
            return new StringPattern(PatternType.Text, text, _exact, null, null);
        }

    /// <summary>Creates a Pattern which matches a given character.</summary>
    /// <param name="text">char to match. The match is exact</param>
        public static implicit operator Pattern(char text)
        {
            return new StringPattern(PatternType.Text, text.ToString(), true, null, null);
        }

    /// <summary>Creates a Pattern which matches any character lying between (and 
    /// including) the two given chars in Unicode sort order.</summary>
    /// <param name="lower">char defining the lower end of the span.</param>
    /// <param name="upper">char defining the upper end of the span.</param>
        public static Pattern Span(char lower, char upper)
        {
            return new StringPattern(PatternType.Span, new string(new char[] {lower, upper}), true, null, null);
        }

    /// <summary>Creates a Pattern which matches any character in the given text.</summary>
    /// <param name="text">string to match a character from.</param>
    /// <param name="exact">bool indicating whether case and diacritical marks should be
    /// respected.</param>
    /// <param name="count">PatternCount to be set to the index of the matched character when
    /// the Pattern is last encountered.</param>
        public static Pattern AnyOf(string text, bool exact, PatternCount count)
        {
            return new StringPattern(PatternType.AnyOf, text, exact, count, null);
        }

    /// <summary>Creates a Pattern which matches any character in the given text.</summary>
    /// <param name="text">string to match a character from.</param>
    /// <param name="exact">bool indicating whether case and diacritical marks should be
    /// respected.</param>
        public static Pattern AnyOf(string text, bool exact)
        {
            return new StringPattern(PatternType.AnyOf, text, exact, null, null);
        }

    /// <summary><para>Creates a Pattern which matches any character in the given text.</para>
    /// <para>Case and diacritical marks will be respected if the static Pattern property
    /// Exact is set to true.</para></summary>
    /// <param name="text">string to match a character from.</param>
    /// <param name="count">PatternCount to be set to the index of the matched character when
    /// the Pattern is last encountered.</param>
        public static Pattern AnyOf(string text, PatternCount count)
        {
            return new StringPattern(PatternType.AnyOf, text, _exact, count, null);
        }

    /// <summary><para>Creates a Pattern which matches any character in the given text.</para>
    /// <para>Case and diacritical marks will be respected if the static Pattern property
    /// Exact is set to true.</para></summary>
     /// <param name="text">string to match a character from.</param>
        public static Pattern AnyOf(string text)
        {
            return new StringPattern(PatternType.AnyOf, text, _exact, null, null);
        }

    /// <summary>Creates a Pattern which matches any character not in the given text.</summary>
    /// <param name="text">string to not match any character from.</param>
    /// <param name="exact">bool indicating whether case and diacritical marks should be
    /// respected.</param>
        public static Pattern AnyBut(string text, bool exact)
        {
            return new StringPattern(PatternType.AnyBut, text, exact, null, null);
        }

    /// <summary><para></para>Creates a Pattern which matches any character not in the given text.</para>
    /// <para>Case and diacritical marks will be respected if the static Pattern property
    /// Exact is set to true.</para></summary>
    /// <param name="text">string to not match any character from.</param>
        public static Pattern AnyBut(string text)
        {
            return new StringPattern(PatternType.AnyBut, text, _exact, null, null);
        }

    /// <summary>Creates a Pattern which matches against the text in a given Range, for example
    /// set by the Save Pattern.</summary>
    /// <param name="range">Range to compare against.</param>
    /// <param name="exact">bool indicating whether case and diacritical marks should be
    /// respected.</param>
        public static Pattern Same(Range range, bool exact)
        {
            return new StringPattern(PatternType.Same, "", exact, null, range);
        }

    /// <summary><para>Creates a Pattern which matches against the text in a given Range, for example
    /// set by the Save Pattern.</para>
    /// <para>Case and diacritical marks will be respected if the static Pattern property
    /// Exact is set to true.</para></summary>
    /// <param name="range">Range to compare against.</param>
        public static Pattern Same(Range range)
        {
            return new StringPattern(PatternType.Same, "", _exact, null, range);
        }

    /// <summary>Creates a Pattern which matches multiple occurrences of a Pattern. If the
    /// minimum count is less than the maximum, the search will recurse over number of matches.
    /// The recursion moves forwards only, so earlier matches of the pattern are not recursed 
    /// over.</summary>
    /// <param name="pattern">Pattern to be matched repeatedly.</param>
    /// <param name="minimum">Minimum number of times to match.</param>
    /// <param name="maximum">Maximum number of times to match or less than minimum to match as
    /// many times as possible.</param>
        public static Pattern Repeat(Pattern pattern, int minimum, int maximum)
        {
            return new RepeatPattern(pattern, minimum, maximum, null);
        }

    /// <summary>Creates a Pattern which matches multiple occurrences of a Pattern and returns 
    /// the actual number of matches. If the minimum count is less than the maximum, the search 
    /// will recurse over number of matches. The recursion moves forwards only, so earlier 
    /// matches of the pattern are not recursed over.</summary>
    /// <param name="pattern">Pattern to be matched repeatedly.</param>
    /// <param name="minimum">Minimum number of times to match.</param>
    /// <param name="maximum">Maximum number of times to match or less than minimum to match as
    /// many times as possible.</param>
    /// <param name="count">PatternCount to be set to the actual number of times the pattern 
    /// was matched when it was last encountered.</param>
        public static Pattern Repeat(Pattern pattern, int minimum, int maximum, PatternCount count)
        {
            return new RepeatPattern(pattern, minimum, maximum, count);
        }

    /// <summary>Creates a Pattern which matches multiple occurrences of a Pattern. If the
    /// minimum count is less than the maximum, the search will recurse over number of matches.
    /// The recursion moves forwards only, so earlier matches of the pattern are not recursed 
    /// over.</summary>
    /// <param name="minimum">Minimum number of times to match.</param>
    /// <param name="maximum">Maximum number of times to match or less than minimum to match as 
    /// many times as possible.</param>
        public Pattern this[int minimum, int maximum]
        {
            get { return new RepeatPattern(this, minimum, maximum, null); }
        }

    /// <summary>Creates a Pattern which matches multiple occurrences of a Pattern.</summary>
    /// <param name="pattern">Pattern to repeat.</param>
    /// <param name="repeat">Exact number of times to match, or negative to match as many times
    /// as possible (in which case the search always returns true).</param>
        public static Pattern operator *(Pattern pattern, int repeat)
        {
            if (repeat < 0) return new RepeatPattern(pattern, 0, repeat, null);
            else return new RepeatPattern(pattern, repeat, repeat, null);
        }

    /// <summary>Creates a Pattern which matches a series of Patterns one after the other. The
    /// sequence of Patterns may be recursed over, so that if there is more than one way to match
    /// the first Pattern, then the subsequent Patterns may be visited more than once.</summary>
    /// <param name="patterns">Two or more Patterns to be combined.</param>
        public static Pattern And(params Pattern[] patterns)
        {
            return new MetaPattern(PatternType.And, null, null, patterns);
        }

    /// <summary>Creates a Pattern which matches one Pattern followed by another. The
    /// sequence of Patterns may be recursed over, so that if there is more than one way to match
    /// the first Pattern, then the subsequent Patterns may be visited more than once.</summary>
    /// <param name="pattern1">First Pattern to be matched.</param>
    /// <param name="pattern2">Subsequent Pattern to be matched.</param>
        public static Pattern operator &(Pattern pattern1, Pattern pattern2)
        {
            return new MetaPattern(PatternType.And, null, null, pattern1, pattern2);
        }

    /// <summary>Creates a Pattern which finds a match among a set of alternative Patterns at
    /// the current search cursor. The first Pattern is tested first, then the second is tested
    /// only if the first does not match. If the first Pattern is matched but a following Pattern
    /// fails to match, the search will recurse, and the second Pattern will be tested.</summary>
    /// <param name="patterns">Two or more alternative Patterns to be tested.</param>
        public static Pattern Or(params Pattern[] patterns)
        {
            return new MetaPattern(PatternType.Or, null, null, patterns);
        }

    /// <summary>Creates a Pattern which finds a match among a set of alternative Patterns at
    /// the current search cursor. The first Pattern is tested first, then the second is tested
    /// only if the first does not match. If the first Pattern is matched but a following Pattern
    /// fails to match, the search will recurse, and the second Pattern will be tested.</summary>
    /// <param name="count">PatternCount to be set to the index of the Pattern which was matched.
    /// </param>
    /// <param name="patterns">Two or more alternative Patterns to be tested.</param>
        public static Pattern Or(PatternCount count, params Pattern[] patterns)
        {
            return new MetaPattern(PatternType.Or, count, null, patterns);
        }

    /// <summary>Creates a Pattern which finds a match for either of two Patterns at the current
    /// search cursor. The first Pattern is tested first, then the second is tested only if the
    /// first does not match. If the first Pattern is matched but a following Pattern fails to
    /// match, the search will recurse, and the second Pattern will be tested.</summary>
    /// <param name="pattern1">First Pattern to be tested.</param>
    /// <param name="pattern2">Second Pattern to be tested if the first Pattern fails to match.
    /// </param>
        public static Pattern operator |(Pattern pattern1, Pattern pattern2)
        {
            return new MetaPattern(PatternType.Or, null, null, pattern1, pattern2);
        }

    /// <summary>Creates a Pattern which finds a match only if the given Pattern does not match. 
    /// The search cursor is not moved.</summary>
    /// <param name="pattern">Pattern to not match.</param>
        public static Pattern Not(Pattern pattern)
        {
            return new MetaPattern(PatternType.Not, null, null, pattern);
        }

    /// <summary>Creates a Pattern which finds a match only if the given Pattern does not match.
    /// The search cursor is not moved.</summary>
    /// <param name="pattern">Pattern to not match.</param>
        public static Pattern operator ~(Pattern pattern)
        {
            return new MetaPattern(PatternType.Not, null, null, pattern);
        }

    /// <summary>Creates a Pattern which saves the result of a successful match into a Range.
    /// </summary>
    /// <param name="pattern">Pattern which must match.</param>
    /// <param name="range">Range to hold the span of the match.</param>
        public static Pattern Save(Pattern pattern, Range range)
        {
            return new MetaPattern(PatternType.Save, null, range, pattern);
        }

    /// <summary>Creates a Pattern which saves the result of a successful match into a Range.
    /// </summary>
    /// <param name="pattern">Pattern which must match.</param>
    /// <param name="range">Range to hold the span of the match.</param>
        public static Pattern operator %(Pattern pattern, Range range)
        {
            return new MetaPattern(PatternType.Save, null, range, pattern);
        }

    /// <summary>Creates a Pattern which always matches, and sets the value of a PatternCount.
    /// </summary>
    /// <param name="count">PatternCount whose value is set when the Pattern is reached.</param>
    /// <param name="value">int value to set the PatternCount to.</param>
        public static Pattern Set(PatternCount count, int value)
        {
            return new CountPattern(PatternType.Set, count, null, value);
        }

    /// <summary>Creates a Pattern which always matches, and sets the value of a PatternCount.
    /// </summary>
    /// <param name="count1">PatternCount whose value is set when the Pattern is reached.</param>
    /// <param name="count2">PatternCount whose current value is used.</param>
        public static Pattern Set(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.Set, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which always matches, and increments the value of a 
    /// PatternCount. Note that the increment occurs even if the current recursive branch of the
    /// search, or the whole search, fails.</summary>
    /// <param name="count">PatternCount whose value is incremented when the Pattern is reached.
    /// </param>
    /// <param name="value">int value to increment the PatternCount by.</param>
        public static Pattern Plus(PatternCount count, int value)
        {
            return new CountPattern(PatternType.Plus, count, null, value);
        }

    /// <summary>Creates a Pattern which always matches, and increments the value of a 
    /// PatternCount. Note that the increment occurs even if the current recursive branch of the
    /// search, or the whole search, fails.</summary>
    /// <param name="count">PatternCount whose value is incremented by 1 when the Pattern is 
    /// reached.</param>
        public static Pattern Plus(PatternCount count)
        {
            return new CountPattern(PatternType.Plus, count, null, 1);
        }

    /// <summary>Creates a Pattern which always matches, and increments the value of a 
    /// PatternCount. Note that the increment occurs even if the current recursive branch of the
    /// search, or the whole search, fails.</summary>
    /// <param name="count1">PatternCount whose value is incremented when the Pattern is reached.
    /// </param>
    /// <param name="count2">PatternCount whose current value is used.</param>
        public static Pattern Plus(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.Plus, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which always matches, and decrements the value of a 
    /// PatternCount. Note that the decrement occurs even if the current recursive branch of the
    /// search, or the whole search, fails.</summary>
    /// <param name="count">PatternCount whose value is decremented when the Pattern is reached.
    /// </param>
    /// <param name="value">int value to decrement the PatternCount by.</param>
        public static Pattern Minus(PatternCount count, int value)
        {
            return new CountPattern(PatternType.Minus, count, null, value);
        }

    /// <summary>Creates a Pattern which always matches, and decrements the value of a 
    /// PatternCount. Note that the decrement occurs even if the current recursive branch of the
    /// search, or the whole search, fails.</summary>
    /// <param name="count">PatternCount whose value is decremented by 1 when the Pattern is 
    /// reached.</param>
        public static Pattern Minus(PatternCount count)
        {
            return new CountPattern(PatternType.Minus, count, null, 1);
        }

    /// <summary>Creates a Pattern which always matches, and decrements the value of a 
    /// PatternCount. Note that the decrement occurs even if the current recursive branch of the
    /// search, or the whole search, fails.</summary>
    /// <param name="count1">PatternCount whose value is decremented when the Pattern is reached.
    /// </param>
    /// <param name="count2">PatternCount whose current value is used.</param>
        public static Pattern Minus(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.Minus, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which matches according to the value of a PatternCount.</summary>
    /// <param name="count">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="value">int value to compare the PatternCount to.</param>
        public static Pattern Equals(PatternCount count, int value)
        {
            return new CountPattern(PatternType.Equals, count, null, value);
        }

    /// <summary>Creates a Pattern which matches according to the comparitive values of two PatternCounts.</summary>
    /// <param name="count1">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="count2">PatternCount whose value is compared.</param>
        public static Pattern Equals(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.Equals, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which matches according to the value of a PatternCount.</summary>
    /// <param name="count">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="value">int value to compare the PatternCount to.</param>
        public static Pattern NotEquals(PatternCount count, int value)
        {
            return new CountPattern(PatternType.NotEqual, count, null, value);
        }

    /// <summary>Creates a Pattern which matches according to the comparitive values of two PatternCounts.</summary>
    /// <param name="count1">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="count2">PatternCount whose value is compared.</param>
        public static Pattern NotEquals(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.NotEqual, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which matches according to the value of a PatternCount.</summary>
    /// <param name="count">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="value">int value to compare the PatternCount to.</param>
        public static Pattern Less(PatternCount count, int value)
        {
            return new CountPattern(PatternType.Less, count, null, value);
        }

    /// <summary>Creates a Pattern which matches according to the comparitive values of two PatternCounts.</summary>
    /// <param name="count1">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="count2">PatternCount whose value is compared.</param>
        public static Pattern Less(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.Less, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which matches according to the value of a PatternCount.</summary>
    /// <param name="count">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="value">int value to compare the PatternCount to.</param>
        public static Pattern Greater(PatternCount count, int value)
        {
            return new CountPattern(PatternType.Greater, count, null, value);
        }

    /// <summary>Creates a Pattern which matches according to the comparitive values of two PatternCounts.</summary>
    /// <param name="count1">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="count2">PatternCount whose value is compared.</param>
        public static Pattern Greater(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.Greater, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which matches according to the value of a PatternCount.</summary>
    /// <param name="count">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="value">int value to compare the PatternCount to.</param>
        public static Pattern LessEqual(PatternCount count, int value)
        {
            return new CountPattern(PatternType.LessEqual, count, null, value);
        }

    /// <summary>Creates a Pattern which matches according to the comparitive values of two PatternCounts.</summary>
    /// <param name="count1">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="count2">PatternCount whose value is compared.</param>
        public static Pattern LessEqual(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.LessEqual, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which matches according to the value of a PatternCount.</summary>
    /// <param name="count">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="value">int value to compare the PatternCount to.</param>
        public static Pattern GreaterEqual(PatternCount count, int value)
        {
            return new CountPattern(PatternType.GreaterEqual, count, null, value);
        }

    /// <summary>Creates a Pattern which matches according to the comparitive values of two PatternCounts.</summary>
    /// <param name="count1">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="count2">PatternCount whose value is compared.</param>
        public static Pattern GreaterEqual(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.GreaterEqual, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which matches according to the return from a PatternDelegate.
    /// The PatternDelegate function is passed a Mark containing the current search cursor position
    /// and must return a bool value indicating a match. If the return value is true, the second
    /// Mark argument must be set to the end of the matched span.</summary>
    /// <param name="del">PatternDelegate to be called when the Pattern is reached.</param>
        public static Pattern Delegate(PatternDelegate del)
        {
            return new DelegatePattern(del, null);
        }

    /// <summary>Creates a Pattern which matches according to the return from a PatternDelegate.
    /// The PatternDelegate function is passed a Mark containing the current search cursor position
    /// and must return a bool value indicating a match. If the return value is true, the second
    /// Mark argument must be set to the end of the matched span. The delegate may also set an
    /// integer value.</summary>
    /// <param name="del">PatternDelegate to be called when the Pattern is reached.</param>
    /// <param name="count">PatternCount to be set to the returned integer value if a match was
    /// found.</param>
        public static Pattern Delegate(PatternDelegate del, PatternCount count)
        {
            return new DelegatePattern(del, count);
        }

    // --------------------------------------------------------------------------------------------

    // Derived Patterns for convenience

    /// <summary>Creates a Pattern which matches any printing character as determined by
    /// Char.IsWhiteSpace() and Char.IsControl().</summary>
        public static Pattern Black()
        {
            return Pattern.And(~Pattern.White(), ~Pattern.Control(), Pattern.Any());
        }

    /// <summary>Creates a Pattern which matches a 7-bit (Basic Latin) letter.</summary>
        public static Pattern Letter7()
        {
            return Pattern.Lower7() | Pattern.Upper7();
        }

    /// <summary>Creates a Pattern which matches a 7-bit (Basic Latin) upper case letter.</summary>
        public static Pattern Upper7()
        {
            return Pattern.Span('A', 'Z');
        }

    /// <summary>Creates a Pattern which matches a 7-bit (Basic Latin) lower case letter.</summary>
        public static Pattern Lower7()
        {
            return Pattern.Span('a', 'z');
        }

    /// <summary>Creates a Pattern which matches a 7-bit (Basic Latin) digit.</summary>
        public static Pattern Digit7()
        {
            return Pattern.Span('0', '9');
        }

    /// <summary>Creates a Pattern which matches a 7-bit (Basic Latin) control character.</summary>
        public static Pattern Control7()
        {
            return Pattern.Span('\u0000', '\u001F') | Pattern.Text("\u007F");
        }

    /// <summary>Creates a Pattern which matches a 7-bit (Basic Latin) symbol character.</summary>
        public static Pattern Symbol7()
        {
            return Pattern.AnyOf("$+<=>^`|~");
        }

    /// <summary>Creates a Pattern which matches a 7-bit (Basic Latin) punctuation character.</summary>
        public static Pattern Punctuation7()
        {
            return Pattern.AnyOf("!\"#%&'()*,-./:;?@[\\]_{}");
        }

    /// <summary>Creates a Pattern which matches a 7-bit (Basic Latin) whitespace character.</summary>
        public static Pattern White7()
        {
            return Pattern.AnyOf(" \t\n\v\f\r");  // Not really expecting \v \f or \r ...
        }

    /// <summary>Creates a Pattern which matches a 7-bit (Basic Latin) printing character.</summary>
        public static Pattern Black7()
        {
            return Pattern.Span('!', '~');
        }

    /// <summary>Creates a Pattern which greedily matches a non-empty sequence of whitespace characters
    /// as defined by Char.IsWhiteSpace().</summary>
        public static Pattern Lacuna()
        {
            return Pattern.White()[1, -1];
        }

    /// <summary>Creates a Pattern which greedily matches a non-empty sequence of 7-bit (Basic Latin) 
    /// whitespace characters.</summary>
        public static Pattern Lacuna7()
        {
            return Pattern.White7()[1, -1];
        }

    /// <summary>Creates a Pattern which greedily matches a non-empty sequence of whitespace characters
    /// as defined by Char.IsWhiteSpace(), but not including newline.</summary>
        public static Pattern Gap()
        {
            return (Pattern.Not("\n") & Pattern.White())[1, -1];
        }

    /// <summary>Creates a Pattern which greedily matches a non-empty sequence of 7-bit (Basic Latin) 
    /// whitespace characters, but not including newline.</summary>
        public static Pattern Gap7()
        {
            return Pattern.AnyOf(" \t\v\f\r")[1, -1];
        }

    /// <summary>Creates a Pattern which matches an integer value: {+|-}9... .</summary>
        public static Pattern Int()
        {
            return (Pattern.AnyOf("+-") | Pattern.BeginWord()) & Pattern.Digit7()[1, -1];
        }

    /// <summary>Creates a Pattern which matches an integer value: {+|-}9... and returns the
    /// value in a PatternCount.</summary>
    /// <param name="count">PatternCount which will be set to the value of the integer if the
    /// match is successful.</param>
        public static Pattern Int(PatternCount count)
        {
            Pattern pInt = Pattern.Int();

        // Anonymous delegate to handle the extraction of the value
            PatternDelegate del = delegate(Mark start, Mark end, ref int value)
            {
                if (pInt.FindFirst(start,end))
                {
                    int.TryParse((start+end).ToString(), out value);
                    return true;
                }
                else return false;
            };

            return Pattern.Delegate(del, count);
        }

    /// <summary>Creates a Pattern which matches a float value: 
    /// {+|-}(9...{.{9...}}|.9...){(e|E){+|-}9...}</summary>
        public static Pattern Float()
        {
            Pattern digit = Pattern.Digit7();
            return Pattern.And(
                        Pattern.AnyOf("+-") | BeginWord(),
                        Pattern.Or(
                            digit[1, -1] & ("." & digit[0, -1] | true),
                            "." & digit[1, -1]
                        ),
                        Pattern.Or(
                            Pattern.And(
                                Pattern.AnyOf("eE"),
                                Pattern.AnyOf("+-") | true,
                                digit[1, -1]
                            ),
                            true
                        )
                    );
        }

    /// <summary>Creates a Pattern which matches a word - letters, digits and underscores
    /// surrounded by non-word characters.</summary>
        public static Pattern Word()
        {
            return Pattern.And ( Pattern.BeginWord(),
                                 Pattern.Repeat(Pattern.Or(Pattern.Letter(),
                                                           Pattern.Digit(),
                                                           Pattern.Text("_")), 1, -1));
        }

    /// <summary>Creates a Pattern which matches a 7-bit (Basic Latin) word - letters, digits 
    /// and underscores surrounded by non-word characters.</summary>
        public static Pattern Word7()
        {
            return Pattern.And ( Pattern.BeginWord7(),
                                 Pattern.Repeat(Pattern.Or(Pattern.Lower7(),
                                                           Pattern.Upper7(),
                                                           Pattern.Digit7(),
                                                           Pattern.Text("_")), 1, -1));
        }

    /// <summary>Creates a Pattern which matches a name - letters, digits and underscores
    /// surrounded by non-word characters, starting with a letter or underscore.</summary>
        public static Pattern Name()
        {
            return Pattern.And ( Pattern.BeginWord(),
                                 Pattern.Or(Pattern.Letter(), Pattern.Text("_")),
                                 Pattern.Repeat(Pattern.Or(Pattern.Letter(),
                                                           Pattern.Digit(),
                                                           Pattern.Text("_")), 0, -1));
        }

    /// <summary>Creates a Pattern which matches a 7-bit (Basic Latin) name - letters, 
    /// digits and underscores surrounded by non-word characters, starting with a letter 
    /// or underscore.</summary>
        public static Pattern Name7()
        {
            return Pattern.And ( Pattern.BeginWord7(),
                                 Pattern.Or(Pattern.Lower7(), Pattern.Upper7(), Pattern.Text("_")),
                                 Pattern.Repeat(Pattern.Or(Pattern.Lower7(),
                                                           Pattern.Upper7(),
                                                           Pattern.Digit7(),
                                                           Pattern.Text("_")), 0, -1));
        }

    /// <summary>Creates a Pattern which matches a delimited string, starting when one delimiter
    /// pattern starts, and ending at the end of another delimiter.</summary>
    /// <param name="start">Pattern which matches the start of the delimited string.</param>
    /// <param name="end">Pattern which matches the end of the delimited string.</param>
        public static Pattern DelimitedString(Pattern start, Pattern end)
        {
            return Pattern.And ( start,
                                 Pattern.Repeat(
                                    Pattern.And(
                                        Pattern.Not(end),
                                        Pattern.Any()),
                                    0, -1),
                                 end );
        }

    /// <summary>Creates a Pattern which matches a delimited string, starting when one delimiter
    /// pattern starts, and ending at the end of another delimiter, but ignoring end delimiters
    /// which are escaped.</summary>
    /// <param name="start">Pattern which matches the start of the delimited string.</param>
    /// <param name="end">Pattern which matches the end of the delimited string.</param>
    /// <param name="escape">Pattern which can be consumed without terminating the string.
    /// </param>
        public static Pattern DelimitedString(Pattern start, Pattern end, Pattern escape)
        {
            return Pattern.And ( start,
                                 Pattern.Repeat(
                                    Pattern.Or(
                                        escape,
                                        Pattern.And(
                                            Pattern.Not(end),
                                            Pattern.Any())),
                                    0, -1),
                                 end );
        }

    //---------------------------------------------------------------------------------------------

    /// <summary>Returns a string describing the Pattern.</summary>
        public override string ToString()
        {
            return ToString(0);
        }
        internal virtual string ToString(int indent)
        {
            return String.Concat(new string(' ',indent), _patternType.ToString());
        }

    /// <summary>Returns a unique ID for the Pattern.</summary>
        public override int GetHashCode()
        {
            return _ID;
        }

    // Takes a deep copy of a Pattern if necessary, in case the calling code is re-using it (which
    // isn't necessary for simple patterns)
        internal virtual Pattern Copy()
        {
            return this;
        }

    // Checks for a match for the Pattern starting from the given mark, and if it matches, sets the
    // end mark and returns true
        internal virtual bool FindFirst(Mark start, Mark end)
        {
            end.MoveTo(start);
            Mark mark;

            char test = ' ';

        // Branch on the PatternType
            switch(_patternType)
            {
                case PatternType.True:
                    return true;

                case PatternType.False:
                    return false;

            // For BeginLine we look back at the previous character but don't step back
                case PatternType.BeginLine:
                    mark = new Mark(end, false);
                    if (!mark.PreviousChar(ref test) || test == '\n')
                        return true;
                    else
                        return false;

            // For EndLine we look at the next character but don't step forward
                case PatternType.EndLine:
                    mark = new Mark(end, false);
                    if (!mark.NextChar(ref test) || test == '\n')
                        return true;
                    else
                        return false;

            // For BeginWord we look backwards for a non-word char and forwards for a word char
                case PatternType.BeginWord:
                    mark = new Mark(end, false);
                    if (mark.PreviousChar(ref test) &&
                        (Char.IsLetter(test) || Char.IsDigit(test) || test=='_'))
                                                                            return false;
                    mark.MoveTo(end);
                    if (mark.NextChar(ref test) &&
                        (Char.IsLetter(test) || Char.IsDigit(test) || test=='_'))
                                                                            return true;
                    return false;

            // Same for BeginWord7 but with quicker tests
                case PatternType.BeginWord7:
                    mark = new Mark(end, false);
                    if (mark.PreviousChar(ref test) &&
                        (test>='a' && test<='z' || test>='A' && test<='Z' || test>='0' && test<='9' || test=='_'))
                                                                                                            return false;
                    mark.MoveTo(end);
                    if (mark.NextChar(ref test) &&
                        (test>='a' && test<='z' || test>='A' && test<='Z' || test>='0' && test<='9' || test=='_'))
                                                                                                            return true;
                    return false;

            // For EndWord we look backwards for a word char and forwards for a non-word char
                case PatternType.EndWord:
                    mark = new Mark(end, false);
                    if (mark.NextChar(ref test) &&
                        (Char.IsLetter(test) || Char.IsDigit(test) || test=='_'))
                                                                            return false;
                    mark.MoveTo(end);
                    if (mark.PreviousChar(ref test) &&
                        (Char.IsLetter(test) || Char.IsDigit(test) || test=='_'))
                                                                            return true;
                        return false;

            // Same for EndWord7 but with quicker tests
                case PatternType.EndWord7:
                    mark = new Mark(end, false);
                    if (mark.NextChar(ref test) &&
                        (test>='a' && test<='z' || test>='A' && test<='Z' || test>='0' && test<='9' || test=='_'))
                                                                                                            return false;
                    mark.MoveTo(end);
                    if (mark.PreviousChar(ref test) &&
                        (test>='a' && test<='z' || test>='A' && test<='Z' || test>='0' && test<='9' || test=='_'))
                                                                                                            return true;
                        return false;

                case PatternType.Any:
                    return (end.NextChar(ref test));

                case PatternType.Letter:
                    return (end.NextChar(ref test) && Char.IsLetter(test));

                case PatternType.Upper:
                    return (end.NextChar(ref test) && Char.IsUpper(test));

                case PatternType.Lower:
                    return (end.NextChar(ref test) && Char.IsLower(test));

                case PatternType.Digit:
                    return (end.NextChar(ref test) && Char.IsDigit(test));

                case PatternType.Control:
                    return (end.NextChar(ref test) && Char.IsControl(test));

                case PatternType.Punctuation:
                    return (end.NextChar(ref test) && Char.IsPunctuation(test));

                case PatternType.Symbol:
                    return (end.NextChar(ref test) && Char.IsSymbol(test));

                case PatternType.White:
                    return (end.NextChar(ref test) && Char.IsWhiteSpace(test));

                // Other PatternTypes are handled in derived classes
                default:
                    return false;
            }

        }

    // For simple patterns, trying again from the same point never makes any difference
        internal virtual bool FindAgain(Mark end)
        {
            return false;
        }
    }

//=================================================================================================

// Pattern class for the Text, AnyOf, AnyBut and Span patterns which need a string, and the Same
// pattern which needs a Range which we convert to string as required
    internal class StringPattern : Pattern
    {
        internal string _text;          // Text for Text, AnyOf, AnyBut
        internal Range _range;          // or Range for Same
        internal bool _exact;           // Ignore case and diacriticals
        internal PatternCount _count;   // Return index of match for AnyOf

        internal StringPattern(PatternType patternType, string text, bool exact, 
                                PatternCount count, Range range) : base(patternType)
        {
            if (exact)
                _text = text;
            else
                _text = Standardise(text);
            _exact = exact;
            _count = count;
            _range = range;
        }

    // Converts to string showing type, string contents and exact flag
        internal override string ToString(int indent)
        {
            StringBuilder sb = new StringBuilder(new string(' ',indent));
            sb.Append(_patternType.ToString());
            if (_patternType==PatternType.Same)
                sb.Append(String.Format("(range #{0}", _range.GetHashCode()));
            else if (_patternType==PatternType.Span)
                sb.Append(String.Format("({0}-{1}", _text[0], _text[1]));
            else
                sb.Append(String.Format("(\"{0}\"", _text));
            if (_patternType!=PatternType.Span) sb.Append(String.Format(",exact={0}", _exact));
            if (_patternType == PatternType.AnyOf && (Object)_count != null)
                sb.Append(String.Format(",count #{0}", _count.GetHashCode()));
            sb.Append(")");
            return sb.ToString();
        }

    // Checks for a match for the Pattern starting from the given mark, and if it matches, sets the
    // end mark and returns true
        internal override bool FindFirst(Mark start, Mark end)
        {
            end.MoveTo(start);
            char test = ' ';

        // Branch on the PatternType
            switch (_patternType)
            {
            // Span - match any character between the two characters in the list
                case PatternType.Span:
                    if (!end.NextChar(ref test)) return false;
                    return (test >= _text[0] && test <= _text[1]);

            // AnyOf - match any character in the list, and return which one
                case PatternType.AnyOf:
                    if (!end.NextChar(ref test)) return false;
                    if (!_exact) test = Standardise(test);
                    for (int i=0; i<_text.Length; i++)
                        if (test==_text[i])
                        {
                            if ((Object)_count != null) _count._value = i;
                            return true;
                        }
                    return false;

            // AnyBut - match any character which is not in the list
                case PatternType.AnyBut:
                    if (!end.NextChar(ref test)) return false;
                    if (!_exact) test = Standardise(test);
                    for (int i=0; i<_text.Length; i++)
                        if (test==_text[i]) return false;
                    return true;

            // Same is the same as text, but we dynamically get the string to be matched from the
            // range
                case PatternType.Same:
                case PatternType.Text:
                    if (_patternType==PatternType.Same)
                    {
                        _text = _range.ToString();
                        if (!_exact) _text = Standardise(_text);
                    }

                    for (int i=0; i<_text.Length; i++)
                    {
                        if (!end.NextChar(ref test)) return false;
                        if (!_exact) test = Standardise(test);
                        if (test != _text[i]) return false;
                    }
                    return true;

                default:
                    return false;
            }
        }

    // For an inexact search, converts a string to upper case and removes diacritical marks
        internal string Standardise(string text)
        {
            StringBuilder sb = new StringBuilder(text.Length);
            for (int i=0; i<text.Length; i++)
            {
                sb.Append(Standardise(text[i]));
            }
            return sb.ToString();
        }

    // For an inexact search, converts a char to upper case and removes diacritical marks
        internal char Standardise(char c)
        {
            return Char.ToUpper((new string(c,1)).Normalize(NormalizationForm.FormKD)[0]);
        }
    }

//=================================================================================================

// Pattern class for the repeat structure allowing a single Pattern to occur multiple times
    internal class RepeatPattern : Pattern
    {
        internal Pattern _pattern;
        internal int _min;
        internal int _max;
        internal PatternCount _count;
        internal int _current;

        internal RepeatPattern(Pattern pattern, int min, int max, PatternCount count)
                                                                            : base(PatternType.Repeat)
        {
            _pattern = pattern.Copy();
            _min = min;
            _max = max;
            _count = count;
        }

        // Converts to string showing min and max, and the repeated Pattern
        internal override string ToString(int indent)
        {
            string tab = new string(' ', indent);
            string desc;
            if ((Object)_count == null) desc = String.Format("Repeat(min={0},max={1})\n", _min, _max);
            else desc = String.Format("Repeat(min={0},max={1},count #{2})\n", _min, _max, _count.GetHashCode() );
            return String.Concat(tab, desc,
                                 tab, "{\n",
                                 _pattern.ToString(indent+4),
                                 "\n", tab, "}");
        }

        // Takes a deep copy of a Pattern if necessary, in case the calling code is re-using it
        internal override Pattern Copy()
        {
            return new RepeatPattern(_pattern.Copy(), _min, _max, _count);
        }

        // Checks for a match for the Pattern starting from the given mark, and if it matches, sets 
        // the end mark and returns true
        internal override bool FindFirst(Mark start, Mark end)
        {
            end.MoveTo(start);
            Mark next = new Mark(end, false);

            // Loop over tests of the sub-pattern; if false, we have failed
            for (_current=0; _current<_min; _current++)
            {
                if (!_pattern.FindFirst(end, next)) return false;
                end.MoveTo(next);
            }

            // If _max is less than _min we keep going until we fail
            if (_max<_min)
            {
                while (_pattern.FindFirst(end, next))
                {
                    _current++;
                    end.MoveTo(next);
                }
            }

            // Remember where to start for FindAgain
            _searchMark = new Mark(end, false);

            // Return how many matches if required
            if ((Object)_count != null) _count._value = _current;
            return true;
        }

        // Checks for another match for the Pattern and if there is one, sets the end mark and returns true
        internal override bool FindAgain(Mark end)
        {
            // Not going to happen if this was a greedy search or we have already hit the maximum
            if (_current>=_max) return false;

            // Otherwise see if we can find one more from where we left off last time
            if (!_pattern.FindFirst(_searchMark, end)) return false;
            _current++;
            _searchMark.MoveTo(end);

            // Return how many matches if required
            if ((Object)_count != null) _count._value = _current;
            return true;
        }
    }

//=================================================================================================

// Pattern class for And, Or, Not and Save patterns which need a list of Patterns
    internal class MetaPattern : Pattern
    {
        internal Pattern[] _patterns;
        internal PatternCount _count;
        internal Range _range;
        internal int _current;
        internal Mark _restart;

        internal MetaPattern(PatternType patternType, PatternCount count, Range range, 
                                                     params Pattern[] patterns) : base(patternType)
        {
            _patterns = new Pattern[patterns.Length];
            for (int i=0; i<patterns.Length; i++) _patterns[i] = patterns[i].Copy();
            _count = count;
            _range = range;
        }

    // Converts to string showing each of the Patterns
        internal override string ToString(int indent)
        {
            string tab = new string(' ', indent);
            StringBuilder text = new StringBuilder(tab);
            text.Append(_patternType.ToString());
            if (_patternType==PatternType.Save)
            {
                text.Append("(range #");
                text.Append(_range.GetHashCode());
                text.Append(")");
            }
            if (_patternType == PatternType.Or && (Object)_count != null)
            {
                text.Append("(count #");
                text.Append(_count.GetHashCode());
                text.Append(")");
            }
            text.Append("\n");
            text.Append(tab);
            text.Append("{\n");
            for (int i=0; i<_patterns.Length; i++)
            {
                text.Append(_patterns[i].ToString(indent+4));
                if (i<_patterns.Length-1) text.Append(",\n");
            }
            text.Append("\n");
            text.Append(tab);
            text.Append("}");
            return text.ToString();
        }

    // Takes a deep copy of a Pattern if necessary, in case the calling code is re-using it
        internal override Pattern Copy()
        {
            Pattern[] patterns = new Pattern[_patterns.Length];
            for (int i=0; i<patterns.Length; i++) patterns[i] = _patterns[i].Copy();
            return new MetaPattern(_patternType, _count, _range, patterns);
        }

    // Checks for a match for the Pattern starting from the given mark, and if it matches, sets 
    // the end mark and returns true
        internal override bool FindFirst(Mark start, Mark end)
        {
            _current = 0;
            _restart = new Mark(start, false);

        // Branch on the PatternType
            switch (_patternType)
            {
            // And - have to match all the patterns in the list in sequence; we may have to recurse over
            // some of the patterns if we don't find it the first time
                case PatternType.And:
                    Mark next = new Mark(start, false);
                    bool down = true;
                    while (_current<_patterns.Length)
                    {
                        if (down)
                        {
                            if (_patterns[_current].FindFirst(next, end))
                            {
                                _current++;
                                next.MoveTo(end);
                            }
                            else
                            {
                                if (_current==0) return false;
                                _current--;
                                down = false;
                            }
                        }
                        else
                        {
                            if (_patterns[_current].FindAgain(end))
                            {
                                _current++;
                                next.MoveTo(end);
                                down = true;
                            }
                            else
                            {
                                if (_current==0) return false;
                                _current--;
                            }
                        }
                    }
                    return true;

            // Or - check through quitting as soon as we get a match
                case PatternType.Or:

                    while (_current<_patterns.Length)
                    {
                        if (_patterns[_current].FindFirst(start, end))
                        {
                            if ((Object)_count != null) _count._value = _current;
                            return true;
                        }
                        else
                            _current++;
                    }
                    return false;

            // Not - if we get a match then fail - but the end mark must equal the start if success
                case PatternType.Not:
                    if (_patterns[0].FindFirst(start, end)) return false;
                    end.MoveTo(start);
                    return true;

            // Save - pass the test through, and save the result if successful
                case PatternType.Save:
                    if (_patterns[0].FindFirst(start, end))
                    {
                        _range.MoveTo(start, end);
                        return true;
                    }
                    else return false;

                default:
                    return false;
            }
        }

    // Checks for a new match for the Pattern starting from the same point; if it matches, sets 
    // the end mark and returns true
        internal override bool FindAgain(Mark end)
        {

        // Branch on the PatternType
            switch (_patternType)
            {
            // And - try for a new match for the last pattern; if not found, step backwards
                case PatternType.And:
                    _current = _patterns.Length - 1;
                    Mark next = new Mark(_restart, false);

                    if (_patterns[_current].FindAgain(end)) return true;

                    _current--;
                    bool down = false;
                    while (_current<_patterns.Length)
                    {
                        if (down)
                        {
                            if (_patterns[_current].FindFirst(next, end))
                            {
                                _current++;
                                next.MoveTo(end);
                            }
                            else
                            {
                                if (_current==0) return false;
                                _current--;
                                down = false;
                            }
                        }
                        else
                        {
                            if (_patterns[_current].FindAgain(end))
                            {
                                _current++;
                                next.MoveTo(end);
                                down = true;
                            }
                            else
                            {
                                if (_current==0) return false;
                                _current--;
                            }
                        }
                    }
                    return true;

            // Or - check again for the current pattern if any, then look through the rest
                case PatternType.Or:
                    if (_current>=_patterns.Length) return false;
                    if (_patterns[_current].FindAgain(end))
                    {
                        if ((Object)_count != null) _count._value = _current;
                        return true;
                    }

                    _current++;
                    while (_current<_patterns.Length)
                    {
                        if (_patterns[_current].FindFirst(_restart, end))
                        {
                            if ((Object)_count != null) _count._value = _current;
                            return true;
                        }
                        else
                            _current++;
                    }
                    return false;

            // Not - no new matches possible
                case PatternType.Not:
                    return false;

            // Save - pass the test through, and save the result if successful
                case PatternType.Save:
                    if (_patterns[0].FindAgain(end))
                    {
                        _range.MoveTo(_restart, end);
                        return true;
                    }
                    else return false;

                default:
                    return false;
            }
        }
    }

//=================================================================================================

// Pattern class for the Set, Plus, Equals, Greater and Less patterns which need a PatternCount 
// and a value or another PatternCount
    internal class CountPattern : Pattern
    {
        internal PatternCount _count1;
        internal PatternCount _count2;
        internal int _value = 0;

        internal CountPattern(PatternType patternType, PatternCount count1, PatternCount count2, int value) : base(patternType)
        {
            _count1 = count1;
            _count2 = count2;
            _value = value;
        }

    // Converts to string showing the Pattern and fairly unique IDs for the counts or the value
        internal override string ToString(int indent)
        {
            string tab = new string(' ', indent);
            if ((Object)_count2 == null)
                return String.Concat(tab, _patternType.ToString(), "(count #", _count1.GetHashCode(), ", ",
                                                                                               _value, ")");
            else
                return String.Concat(tab, _patternType.ToString(), "(count #", _count1.GetHashCode(), 
                                                                   ", count #", _count2.GetHashCode(), ")");
        }

    // No searching required
        internal override bool FindFirst(Mark start, Mark end)
        {
        // We do not move forward
            end.MoveTo(start);

        // Use/compare to the fixed value or the dynamic second PatternCount
            int value = _value;
            if ((Object)_count2 != null) value = _count2._value;

        // Branch on the PatternType
            switch (_patternType)
            {
            // Set - just set the value
                case PatternType.Set:
                    _count1._value = value;
                    return true;

            // Plus - increment the value; note could be confusing if search recurses
                case PatternType.Plus:
                    _count1._value += value;
                    return true;

            // Minus - decrement the value; note could be confusing if search recurses
                case PatternType.Minus:
                    _count1._value -= value;
                    return true;

            // Equals - compare current value against test value
                case PatternType.Equals:
                    return (_count1._value == value);

            // NotEquals - compare current value against test value
                case PatternType.NotEqual:
                    return (_count1._value != value);

            // Less - compare current value against test value
                case PatternType.Less:
                    return (_count1._value < value);

            // Greater - compare current value against test value
                case PatternType.Greater:
                    return (_count1._value > value);

            // LessEqual - compare current value against test value
                case PatternType.LessEqual:
                    return (_count1._value <= value);

            // GreaterEqual - compare current value against test value
                case PatternType.GreaterEqual:
                    return (_count1._value >= value);

                default:
                    return false;
            }
        }

    // No possible alternate match
        internal override bool FindAgain(Mark end)
        {
            return false;
        }
    }

//=================================================================================================

/// <summary>Type of delegate to be called during a search.</summary>
/// <param name="start">Mark passed in with the current search cursor position.</param>
/// <param name="end">Mark that must be moved to the end of the matched text if the delegate
/// returns True.</param>
/// <param name="count">int that may be returned and used to set a PatternCount on a 
/// successful match, if one was defined when the Pattern was created.</param>
/// <returns>True if the text starting from the search cursor matches, and False otherwise.
/// </returns>
    public delegate bool PatternDelegate(Mark start, Mark end, ref int count);

// Pattern class for the Delegate pattern which holds a delegate to do the work
    internal class DelegatePattern : Pattern
    {
        internal PatternDelegate _del;
        internal PatternCount _count;

        internal DelegatePattern(PatternDelegate del, PatternCount count) : base(PatternType.Delegate)
        {
            _del = del;
            _count = count;
        }

    // Converts to string showing the Pattern 
        internal override string ToString(int indent)
        {
            string tab = new string(' ', indent);
            return String.Concat(tab, _patternType.ToString(), "(", _del.GetHashCode(), ")");
        }

    // Checks for a match for the Pattern starting from the given mark, and if it matches, sets the
    // end mark and returns true
        internal override bool FindFirst(Mark start, Mark end)
        {
        // Avoid confusing behaviour if the delegate sets the start mark or doesn't set the end mark
            Mark start2 = new Mark(start, false);
            end.MoveTo(start);
            int value = 0;

        // If we matched and a PatternCount was passed, set it
            if (_del(start2, end, ref value))
            {
                if ((Object)_count!=null) _count._value = value;
                return true;
            }
            else return false;
        }

    // Assume that we will never match a second time from the same start point
        internal override bool FindAgain(Mark end)
        {
            return false;
        }

    }

//=================================================================================================

/// <summary>Lightweight class used to pass and return integer count and flag values for complex
/// searches.</summary>
    public class PatternCount
    {
        private static int _IDs = 0;    // Number of PatternCounts so far
        private int _ID;                // PatternCount ID for debug

        internal int _value;            // The actual count

    /// <summary>Current value held by the PatternCount.</summary>
        public int Value
        {
            get { return _value; }
            set { _value = value; }
        }

    /// <summary>Creates a PatternCount with an initial value.</summary>
    /// <param name="value">Initial value for the PatternCount.</param>
        public PatternCount(int value)
        {
            _ID = ++_IDs;
            _value = value;
        }

    /// <summary>Creates a PatternCount with an initial value of zero.</summary>
        public PatternCount()
        {
            _ID = ++_IDs;
            _value = 0;
        }

    /// <summary>Creates a Pattern which always matches, and sets the value of a PatternCount.
    /// </summary>
    /// <param name="count">PatternCount whose value is set when the Pattern is reached.</param>
    /// <param name="value">int value to set the PatternCount to.</param>
        public static Pattern operator ^(PatternCount count, int value)
        {
            return new CountPattern(PatternType.Set, count, null, value);
        }

    /// <summary>Creates a Pattern which always matches, and sets the value of a PatternCount.
    /// </summary>
    /// <param name="count1">PatternCount whose value is set when the Pattern is reached.</param>
    /// <param name="count2">PatternCount whose value is used.</param>
        public static Pattern operator ^(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.Set, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which always matches, and increments the value of a 
    /// PatternCount.</summary>
    /// <param name="count">PatternCount whose value is incremented when the Pattern is reached.
    /// </param>
    /// <param name="value">int value to increment the PatternCount by.</param>
        public static Pattern operator +(PatternCount count, int value)
        {
            return new CountPattern(PatternType.Plus, count, null, value);
        }

    /// <summary>Creates a Pattern which always matches, and increments the value of one 
    /// PatternCount by the value of another.</summary>
    /// <param name="count1">PatternCount whose value is incremented when the Pattern is reached.
    /// </param>
    /// <param name="count2">PatternCount whose value is used.</param>
        public static Pattern operator +(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.Plus, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which always matches, and decrements the value of a 
    /// PatternCount.</summary>
    /// <param name="count">PatternCount whose value is decremented when the Pattern is reached.
    /// </param>
    /// <param name="value">int value to decrement the PatternCount by.</param>
        public static Pattern operator -(PatternCount count, int value)
        {
            return new CountPattern(PatternType.Minus, count, null, value);
        }

    /// <summary>Creates a Pattern which always matches, and decrements the value of one 
    /// PatternCount by another.</summary>
    /// <param name="count1">PatternCount whose value is decremented when the Pattern is reached.
    /// </param>
    /// <param name="count2">PatternCount whose value is used.</param>
        public static Pattern operator -(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.Minus, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which matches according to the value of a PatternCount.</summary>
    /// <param name="count">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="value">int value to compare the PatternCount to.</param>
        public static Pattern operator ==(PatternCount count, int value)
        {
            return new CountPattern(PatternType.Equals, count, null, value);
        }

    /// <summary>Creates a Pattern which matches according to the comparitive values of two PatternCounts.</summary>
    /// <param name="count1">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="count2">PatternCount whose value is compared.</param>
    // A bit dodgy but amusing.  Use patternCount.Equals(x) or (Object) patternCount == x for actual reference equality tests.
        public static Pattern operator ==(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.Equals, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which matches according to the value of a PatternCount.</summary>
    /// <param name="count">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="value">int value to compare the PatternCount to.</param>
        public static Pattern operator !=(PatternCount count, int value)
        {
            return new CountPattern(PatternType.NotEqual, count, null, value);
        }

    /// <summary>Creates a Pattern which matches according to the comparitive values of two PatternCounts.</summary>
    /// <param name="count1">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="count2">PatternCount whose value is compared.</param>
    // A bit dodgy but amusing.  Use patternCount.NotEquals(x) or (Object) patternCount != x for actual reference inequality tests.
        public static Pattern operator !=(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.NotEqual, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which matches according to the value of a PatternCount.</summary>
    /// <param name="count">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="value">int value to compare the PatternCount to.</param>
        public static Pattern operator <(PatternCount count, int value)
        {
            return new CountPattern(PatternType.Less, count, null, value);
        }

    /// <summary>Creates a Pattern which matches according to the comparitive values of two PatternCounts.</summary>
    /// <param name="count1">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="count2">PatternCount whose value is compared.</param>
        public static Pattern operator <(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.Less, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which matches according to the value of a PatternCount.</summary>
    /// <param name="count">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="value">int value to compare the PatternCount to.</param>
        public static Pattern operator >(PatternCount count, int value)
        {
            return new CountPattern(PatternType.Greater, count, null, value);
        }

    /// <summary>Creates a Pattern which matches according to the comparitive values of two PatternCounts.</summary>
    /// <param name="count1">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="count2">PatternCount whose value is compared.</param>
        public static Pattern operator >(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.Greater, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which matches according to the value of a PatternCount.</summary>
    /// <param name="count">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="value">int value to compare the PatternCount to.</param>
        public static Pattern operator <=(PatternCount count, int value)
        {
            return new CountPattern(PatternType.LessEqual, count, null, value);
        }

    /// <summary>Creates a Pattern which matches according to the comparitive values of two PatternCounts.</summary>
    /// <param name="count1">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="count2">PatternCount whose value is compared.</param>
        public static Pattern operator <=(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.LessEqual, count1, count2, 0);
        }

    /// <summary>Creates a Pattern which matches according to the value of a PatternCount.</summary>
    /// <param name="count">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="value">int value to compare the PatternCount to.</param>
        public static Pattern operator >=(PatternCount count, int value)
        {
            return new CountPattern(PatternType.GreaterEqual, count, null, value);
        }

    /// <summary>Creates a Pattern which matches according to the comparitive values of two PatternCounts.</summary>
    /// <param name="count1">PatternCount whose value is tested when the Pattern is reached.</param>
    /// <param name="count2">PatternCount whose value is compared.</param>
        public static Pattern operator >=(PatternCount count1, PatternCount count2)
        {
            return new CountPattern(PatternType.GreaterEqual, count1, count2, 0);
        }

    /// <summary>Returns a unique ID for the PatternCount.</summary>
        public override int GetHashCode()
        {
            return _ID;
        }

    /// <summary>Returns the current value of the PatternCount as a string.</summary>
        public override string ToString()
        {
            return _value.ToString();
        }

    }

//=================================================================================================

/// <summary>Specifies the type and direction of a search.</summary>
    public enum SearchType
    {
    /// <summary>Search will move forwards through the Text until a match is found.</summary>
        Forwards,
    /// <summary>Search will move backwards through the Text until a match is found.</summary>
        Backwards,
    /// <summary>Search will test for a match only at one position in the Text.</summary>
        Anchored
    }

//=================================================================================================

/// <summary>Defines a bookmark in a Text which moves with the text.</summary>
    public partial class Mark
    {
    /// <summary>Determines whether the text immediately following the Mark is a match for the Pattern.
    /// </summary>
    /// <param name="pattern">A Pattern to match.</param>
    /// <exception cref="InvalidOperationException">This Mark has been invalidated.</exception>
        public bool Search(Pattern pattern)
        {
            ValidateThis();

            _pattern = pattern;
            Mark end = new Mark(this, false);
            return pattern.FindFirst(this, end);
        }

    /// <summary>After a successful call to Search, determines whether there is another way of 
    /// matching the same Pattern at the same place.</summary>
    /// <exception cref="InvalidOperationException">This Mark has been invalidated.</exception>
        public bool SearchAgain()
        {
            ValidateThis();
            if (_pattern==null)
                throw new InvalidOperationException
                                    ("Cannot SearchAgain if Mark has moved since previous Search.");

            Mark end = new Mark(this, false);
            return _pattern.FindAgain(end);
        }
    }

//=================================================================================================

/// <summary>Defines a span between two Marks in a Text which move with the text</summary>
    public partial class Range
    {

    /// <summary>Searches from one end of the Range to find a match for the Pattern, and moves the
    ///  current cursor if a match is found.</summary>
    /// <param name="pattern">A Pattern to match.</param>
    /// <param name="searchType">A SearchType specifying whether the search is forwards from the
    /// start of the Range, backwards from the end of the Range, or anchored at the start.</param>
    /// <exception cref="InvalidOperationException">This Range has been invalidated.</exception>
        public bool Search(Pattern pattern, SearchType searchType)
        {
            ValidateThis();

            Mark start;
            char next = ' ';

            switch (searchType)
            {
                case SearchType.Forwards:
                    start = new Mark(_mark1, false);
                    while (!start.SameAs(_mark2))
                        if (start.Search(pattern))
                        {
                            _mark1._text.MoveTo(start);
                            return true;
                        }
                        else
                        {
                            start.NextChar(ref next);
                        }
                    return false;

                case SearchType.Backwards:
                    start = new Mark(_mark2, false);
                    while (!start.SameAs(_mark1))
                        if (start.Search(pattern))
                        {
                            _mark1._text.MoveTo(start);
                            return true;
                        }
                        else
                        {
                            start.PreviousChar(ref next);
                        }
                    return false;

                case SearchType.Anchored:
                    if (_mark1.Search(pattern))
                    {
                        _mark1._text.MoveTo(_mark1);
                        return true;
                    }
                    else
                        return false;

                default:
                    return false;
            }
        }

    /// <summary>Searches forwards from the start of the Range to find a match for the Pattern, 
    /// and moves the current cursor if a match is found.</summary>
    /// <param name="pattern">A Pattern to match.</param>
    /// <exception cref="InvalidOperationException">This Range has been invalidated.</exception>
        public bool Search(Pattern pattern)
        {
            return Search(pattern, SearchType.Forwards);
        }

    }

//=================================================================================================

/// <summary>Defines a buffer of text which can be manipulated programmatically.</summary>
    public partial class Text
    {
    /// <summary>Searches from the current cursor to find a match for the Pattern, and moves the
    /// current cursor as necessary if a match is found.</summary>
    /// <param name="pattern">A Pattern to match.</param>
    /// <param name="searchType">A SearchType specifying whether the search is forwards from the
    ///  current cursor, backwards from the cursor, or anchored at the cursor.</param>
        public bool Search(Pattern pattern, SearchType searchType)
        {
            Range range;
            switch (searchType)
            {
                case SearchType.Forwards:
                    range = new Range(_cursor, EndMark(false));
                    return range.Search(pattern, searchType);

                case SearchType.Backwards:
                    range = new Range(StartMark(false), _cursor);
                    return range.Search(pattern, searchType);

                case SearchType.Anchored:
                    return _cursor.Search(pattern);

                default:
                    return false;
            }
        }

    /// <summary>Searches forwards from the current cursor to find a match for the Pattern, and 
    /// moves the current cursor if a match is found.</summary>
    /// <param name="pattern">A Pattern to match.</param>
        public bool Search(Pattern pattern)
        {
            return this.Search(pattern, SearchType.Forwards);
        }
    }
}
